//黄金矿工
/*你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。

为了使收益最大化，矿工需要按以下规则来开采黄金：

每当矿工进入一个单元，就会收集该单元格中的所有黄金。
矿工每次可以从当前位置向上下左右四个方向走。
每个单元格只能被开采（进入）一次。
不得开采（进入）黄金数目为 0 的单元格。
矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。
1 <= grid.length, grid[i].length <= 15
0 <= grid[i][j] <= 100
最多 25 个单元格中有黄金
*/
class Solution {
    int Max = 0;
    bool dig[16][16] = {0};
    int m;
    int n;

public:
    int getMaximumGold(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!grid[i][j])
                    dig[i][j] = true;
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]) {
                    int temp = grid[i][j];
                    dig[i][j] = true;
                    grid[i][j] = 0;
                   // cout << i << '-' << j << endl;
                    dfs(grid, i, j, temp);
                    dig[i][j] = false;
                    grid[i][j] = temp;
                }
            }
        }
        return Max;
    }
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    void dfs(vector<vector<int>>& grid, int i, int j, int sum) {
        Max = max(Max, sum);
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !dig[x][y]) {
                int temp = grid[x][y];
                dig[x][y] = true;
                grid[x][y] = 0;
               // cout << x << '-' << y << endl;
                dfs(grid, x, y, sum + temp);
                dig[x][y] = false;
                grid[x][y] = temp;
            }
        }
    }
};

//优化
class Solution {
    int Max = 0;
   // bool dig[16][16] = {0};
    int m;
    int n;

public:
    int getMaximumGold(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
      /*  for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!grid[i][j])
                    dig[i][j] = true;
            }
        }*/

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]) {
                    int temp = grid[i][j];
                 //   dig[i][j] = true;
                    grid[i][j] = 0;
                   // cout << i << '-' << j << endl;
                    dfs(grid, i, j, temp);
                   // dig[i][j] = false;
                    grid[i][j] = temp;
                }
            }
        }
        return Max;
    }
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    void dfs(vector<vector<int>>& grid, int i, int j, int sum) {
        Max = max(Max, sum);
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y]) {
                int temp = grid[x][y];
               // dig[x][y] = true;
                grid[x][y] = 0;
               // cout << x << '-' << y << endl;
                dfs(grid, x, y, sum + temp);
               // dig[x][y] = false;
                grid[x][y] = temp;
            }
        }
    }
};

//不同路径 III
/*在二维网格 grid 上，有 4 种类型的方格：

1 表示起始方格。且只有一个起始方格。
2 表示结束方格，且只有一个结束方格。
0 表示我们可以走过的空方格。
-1 表示我们无法跨越的障碍。
返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。

每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。
1 <= grid.length * grid[0].length <= 20
*/
class Solution {
    bool visi[21][21] = {0};
    int path = 0;
    int ret = 0;
    int m, n;
    int sum = 0;
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};

public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        int onex, oney;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] != -1) {
                    sum++;
                    if (grid[i][j] == 1) {
                        onex = i;
                        oney = j;
                    }
                }
            }
        }
        // cout<<onex<<"-"<<oney<<endl;
        visi[onex][oney] = true;
        path++;
        dfs(grid, onex, oney);
        return ret;
    }
    void dfs(vector<vector<int>>& grid, int x, int y) {
        if (grid[x][y] == 2) {
            if (path == sum)
                ret++;
            return;
        }
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visi[nx][ny] &&
                grid[nx][ny] != -1) {
                visi[nx][ny] = true; 
                path++;
                dfs(grid, nx, ny);
                path--;              
                visi[nx][ny] = false; 
            }
        }
    }
};